Update an Item - Educational Content

The complexity of updating an item is dominated by the time required to locate the target node.

Since updating an item necessitates first finding the item, the complexity is dominated by the linear search required to locate the target node.
We must traverse the list using pointer $p$ until the node containing value $x$ is found.
This search phase dictates the overall worst-case time complexity: $O(n)$.
Once the target node is located, modifying its value to $y$ is an instantaneous $O(1)$ operation.
The update involves only a direct memory write to the node's item field, requiring no pointer relinking or element shifting.

Complexity Analysis: Update an Item

Operation	Time Complexity	Reason
Locate Target Node	$O(n)$	Requires linear traversal from $head$.
Modify Value Field	$O(1)$	Direct memory write once pointer $p$ is positioned.
Overall Update (by value)	$O(n)$	Dominated by the search phase.

Space complexity remains $O(1)$ as only a single traversal pointer is used.

Animation showing a pointer traversing a linked list (10, 20, 30, 40) to find the node with value 30, and then instantly replacing that value with 99.

Linked List Update (Python)

1class Node:
2    # Reusing Node_Structure: {value, next}
3    def __init__(self, value, next_node=None):
4        self.value = value
5        self.next = next_node
6
7def update_item(head, target_x, new_y):
8    p = head  # Pointer p starts at head
9    
10    # O(n) Search phase
11    while p is not None:
12        if p.value == target_x:
13            # O(1) Update phase
14            p.value = new_y
15            print(f"Updated {target_x} to {new_y}.")
16            return True 
17        
18        p = p.next
19        
20    print(f"Target {target_x} not found.")
21    return False
22
23# Setup list: 10 -> 20 -> 30 -> 40
24head_ex = Node(10, Node(20, Node(30, Node(40))))
25
26# Update 30 to 99
27update_item(head_ex, 30, 99)
28
29# Verification (Traversal print)
30curr = head_ex
31result = []
32while curr is not None:
33    result.append(str(curr.value))
34    curr = curr.next
35print("New list state: " + " -> ".join(result))

Knowledge Check

Why is updating an item in a Linked List typically $O(n)$?

A) Because all subsequent nodes must be shifted.
B) Because the list must be traversed to find the target node.
C) Because the pointer relinking takes linear time.